package com.zxy.leetcode.lcof;

import com.zxy.leetcode.common.ListNode;
import com.zxy.leetcode.common.ListNodeHelper;

/**
 * https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
 *
 * 链表中倒数第k个节点
 * 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，
 * 本题从1开始计数，即链表的尾节点是倒数第1个节点。
 * 例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。
 * 这个链表的倒数第3个节点是值为4的节点。
 */
public class Test22 {

    public static void main(String[] args) {
        Test22 test = new Test22();
        ListNode head = ListNodeHelper.build(5);
        ListNodeHelper.print(head);
        head = test.getKthFromEnd(head, 2);
        ListNodeHelper.print(head);
    }

    public ListNode getKthFromEnd(ListNode head, int k) {
        if (head == null) {
            return head;
        }

        int count = 0;
        ListNode p = head;
        while (p != null) {
            count ++;
            p = p.next;
        }

        p = head;
        for (int i=0; i<count-k; i++) {
            p = p.next;
        }
        return p;
    }
}
